package com.kingwood.algorithm.zuochengyun.tanxin1;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/22 14:25
 * @Modified By：
 * @Version 1.0
 */
// 最大数
// 给定一组非负整数nums
// 重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数
// 测试链接 : https://leetcode.cn/problems/largest-number/
public class Code01_LargestNumber {
    // strs中全是非空字符串，要把所有字符串拼接起来，形成字典序最小的结果
    // 暴力方法
    // 为了验证
    // 生成所有可能的排列
    // 其中选出字典序最小的结果
    public static String way1(String[] strs) {
        ArrayList<String> ans = new ArrayList<>();
        f(strs, 0, ans);
        ans.sort((a, b) -> a.compareTo(b));
        return ans.get(0);
    }

    // 全排列代码，讲解038，常见经典递归过程解析
    public static void f(String[] strs, int i, ArrayList<String> ans) {
        if (i == strs.length) {
            StringBuilder path = new StringBuilder();
            for (String s : strs) {
                path.append(s);
            }
            ans.add(path.toString());
        } else {
            for (int j = i; j < strs.length; j++) {
                swap(strs, i, j);
                f(strs, i + 1, ans);
                swap(strs, i, j);
            }
        }
    }

    public static void swap(String[] strs, int i, int j) {
        String tmp = strs[i];
        strs[i] = strs[j];
        strs[j] = tmp;
    }

    // strs中全是非空字符串，要把所有字符串拼接起来，形成字典序最小的结果
    // 正式方法
    // 时间复杂度O(n*logn)
    public static String way2(String[] strs) {
        Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));
        StringBuilder path = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            path.append(strs[i]);
        }
        return path.toString();
    }

    // 测试链接 : https://leetcode.cn/problems/largest-number/
    public static String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];

        for (int i=0; i<n; i++) {
            strs[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
        if (strs[0].equals("0")) {
            return "0";
        }

        StringBuilder path = new StringBuilder();
        for (String s : strs) {
            path.append(s);
        }

        return path.toString();
    }

}
